Bellman Ford

发表于 | 分类于

Bellman Ford同样是一种单源最短路算法，它的优秀之出在于它可以处理带有负边权的图，我们先来看看核心代码：

1
2
3
4
5
6
7
for(int k = 1; k <= n - 1; k ++) {
	for(int i = 1; i <= m; i++) {
		if(dist[edge[i].to] > dist[edge[i].from] + edge[i].w) {
			dist[edge[i].to] = dist[edge[i].from] + edge[i].w;
		}
	}
}

上面的代码中，外循环一共循环了n - 1次（n为顶点的个数），内循环循环了m次（m为边的个数），dist为源点到其余各点的距离。 

1
2
3
if(dist[edge[i].to] > dist[edge[i].from] + edge[i].w) {
			dist[edge[i].to] = dist[edge[i].from] + edge[i].w;
		}

上面这两行代码的意思是，看看能否通过第i条边，使得源点到第i条边的终点的距离变短。这其实与dijkstra的松弛操作是一样的。现在我们要把所有的边都松弛一遍。

1
2
3
4
5
for(int i = 1; i <= m; i++) {
		if(dist[edge[i].to] > dist[edge[i].from] + edge[i].w) {
			dist[edge[i].to] = dist[edge[i].from] + edge[i].w;
		}
	}

在第1轮对所有边进行松弛之后，得到的是从源点只经过一条边到达其余个顶点的最短路径长度。在第2轮对所有的边进行松弛之后，得到的是从源点最多经过两条边到达其余各顶点的最短路径长度。如果进行k轮的话，得到的就是从源点最多经过k条边到达其余各顶点的最短路径长度。

我们最多进行n-1轮松弛就可以了，因为在一个含n个点的图中，任意两点间的最短路径最多包含n-1条边。

题目链接

热浪大家已经很熟悉了，这道题也可以作为Bellman Ford算法的模板题，大家可以用这道题来检验自己算法的准确性。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <iostream>
#include <cctype>
#define DEBUG(x) std::cerr << #x << "=" << x <<std:: endl
inline int read() {
	char ch = getchar(); int res = 0; int flag = 1;
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') flag = -1;
	for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + ch - '0';
	return (res * flag);
}//快读  需要用到头文件<cctype>
const int N_max = 2500 + 7;
const int M_max = 13000 + 7;
const int INF = 0x3f3f3f3;
int n, m, start, end, num;
int dis[N_max];
struct Edge{
	int from, to, w, next;
}edge[M_max];
inline void add_edge(int from, int to, int w) {
	edge[++num].to = to;
	edge[num].w = w;
	edge[num].from = from;
}
inline int BellmanFord() {
	for(int i = 1; i <= n; i ++) {
		dis[i] = INF;
	}
	dis[start] = 0;
	for(int j = 1; j <= n - 1; j ++) {
		bool check = 0;
		for(int i = 1; i <= 2 * m; i++) {
			if(dis[edge[i].to] > dis[edge[i].from] + edge[i].w) {
				dis[edge[i].to] = dis[edge[i].from] + edge[i].w;
				check = 1;
			}
		}
		if(check == 0) break;//如果这一轮松弛操作中，如果dis数组没有任何变动，
        那么就可以说明所有点的dis值都已经确定了，便可以退出循环。
	}
	return dis[end];
}
int main() {
	n = read(); m = read(); start = read(); end = read();
	for(int i = 1; i <= m; i ++) {
		int x, y, z;
		x = read(); y = read(); z = read();
		add_edge(x, y, z);
		add_edge(y, x, z);
	}
	
	for(int i = 1; i <= 2 * m; i ++) {
		if(dis[edge[i].to] > dis[edge[i].from] + edge[i].w) {
			printf("fuhuan\n");
		}
	} //如果在Bellman Ford跑完后，dis数组仍可以变动，则说明图中存在负环。
	
	printf("%d\n", BellmanFord());
	return 0;
}